class Solution {
    /*
        首先暴力的方法是枚举每个点，判断能否走回起点，时间复杂度O（N*N）。
        所以我们要尽可能减少枚举的次数！！！！
        
        首先 diff[i] = gas[i]-cost[i];
        假设diff = {2,1,-1,-3,5};
        我们从位置0开始走，容易知道走到位置3之前就会停下来，所以我们知道0点是不能返回的，
        那么通过分析知道位置1，位置2，位置3都是不能返回起点的，这样我们就直接枚举
        位置4判断能否回到起点即可。
    */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = cost.length;
        int index = 0;
        while( index<len ){
            int step = get(index,gas,cost);
            if( step==len ){  // 情况1：走了len步，表示能够回到原点
                return index;
            }else if( index+step+1<len ){ // 情况2：不能回到原点，而且最近的不能到达的点没有超出范围
                index = index+step+1;
            }else{ // 情况3：超出范围了，表示到不了
                break;
            }
        }
        return -1;
    }
    public int get(int index,int[] gas, int[] cost){
        int step = 0;
        int sum = 0;
        int len = gas.length;
        while( step<=len-1 ){
            int i = (index+step)%len;
            sum += (gas[i]-cost[i]);
            if( sum<0 ){   // 无法到达
                return step;
            }
            step ++;
        }
        return step;
    }
}